package tests;

public class Keyongyu {
    static class Node {
        int index;
        String data;
        Node next;

        public Node(String data) {
            this.data = data;
        }

        @Override
        public String toString() {
            if (next == null) {
                return "Node{" + data + "}";
            }
            return "Node{" + data + "}->" + next;
        }
    }


    public static Node reverse(Node root) {
        if (root == null || root.next == null)
            return root;
        Node temp = root.next;//初始化的next节点存在临时变量
        Node newRoot = reverse(root.next);//相当于root抽出来，从next开始进行反转
        temp.next = root;//不用管root的next怎么变化，只需要root跟在初始化的next节点后面就行了
        root.next = null;
        return newRoot;
    }

    public static Node getMiddleNode(Node head) {
        Node midNode = head;
        Node tempNode = head;
        //循环结束时lastNode指向最末尾节点，midNode刚好指向中间节点
        while (tempNode.next != null && tempNode.next.next != null) {
            //快慢指针 n2前进2步 n1前进1步
            midNode = midNode.next;
            tempNode = tempNode.next.next;
        }
        return midNode;
    }

    public static boolean isPalindrome(Node head) {
        Node midNode = getMiddleNode(head);//找中间节点
        Node midLastNode = reverse(midNode.next);//中间节点后面的反序
        Node preHalf = head;//前半部分
        Node sufHalf = midLastNode;//后半部分
        while (preHalf.next != null && sufHalf.next != null) {
            if (!preHalf.data.equals(sufHalf.data))
                return false;
            preHalf = preHalf.next;
            sufHalf = sufHalf.next;
        }
        return true;
    }

    public static void main(String[] args) {
        Node root = buildNode(new int[]{1, 2, 3, 4, 5, 6, 7, 6, 5, 4, 7, 8, 9});
        System.out.println("链表:" + root);
        System.out.println("是否是回文字符串:" + isPalindrome(root));
        root = buildNode(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1});
        System.out.println("链表:" + root);
        System.out.println("是否是回文字符串:" + isPalindrome(root));
    }

    public static Node buildNode(int[] datas) {
        Node last = null;
        Node root = null;
        for (int data : datas) {
            Node node = new Node(String.valueOf(data));
            if (last != null) {
                last.next = node;
            } else {
                root = node;
            }
            last = node;
        }
        return root;
    }
}